package practice1_100;

import java.util.HashMap;
import java.util.Map;

public class Practice567 {
    //双指针，用滑动窗口解法，
    public boolean checkInclusion1(String s1, String s2) {
        int left=0,right=0;
        Map<Character,Integer> count =new HashMap<>();
        Map<Character,Integer> actual =new HashMap<>();
        for (int i=0 ;i<s1.length();i++){
            if(!count.containsKey(s1.charAt(i)))
                count.put(s1.charAt(i),1);
            else
                count.put(s1.charAt(i),count.get(s1.charAt(i))+1);
        }
        while (right<s2.length()){
            if(!actual.containsKey(s2.charAt(right)))
                actual.put(s2.charAt(right),1);
            else
                actual.put(s2.charAt(right),actual.get(s2.charAt(right))+1);
            right++;

            //left和right正好隔着一个s1长度时候
            if(right-left==s1.length()){
                if(count.equals(actual)) return true;
                else {
                    //移除left所指的元素,这里有点麻烦，要判断map中该元素为1的情况，为一就直接remove，不唯一就减一
                    if(actual.get(s2.charAt(left))==1)
                        actual.remove(s2.charAt(left));
                    else
                        actual.put(s2.charAt(left),actual.get(s2.charAt(left))-1);
                    left++;
                }
            }
        }
        return false;

    }
    //自己写的暴力算法
    public boolean checkInclusion(String s1, String s2) {
        Map<Character,Integer> count =new HashMap<>();
        Map<Character,Integer> actual =new HashMap<>();
        for (int i=0;i<s1.length();i++){
            if(!count.containsKey(s1.charAt(i))){
                count.put(s1.charAt(i),1);
            }
            else {
                count.put(s1.charAt(i),count.get(s1.charAt(i))+1);
            }
        }


        for (int left=0;left<=s2.length()-s1.length();left++){
            int right=left+ s1.length()-1;
            while (left<=right){
                if(count.get(s2.charAt(right))==0) {
                    actual.clear();
                    continue;
                }else if(!actual.containsKey(s2.charAt(right)))
                    actual.put(s2.charAt(right),1);
                else
                    actual.put(s2.charAt(right),actual.get(s2.charAt(right))+1);
                right--;
            }
            //判断两者是否相等
            if(count.equals(actual)) return true;
            else actual.clear();
        }
    return false;
    }

    public static void main(String[] args) {
        Practice567 practice567 =new Practice567();
        boolean a= practice567.checkInclusion1("abbbc","fghcbabbfjsghfdjgk");
        System.out.println(a);
//        String s1="sdfgg";
//        Map<Character,Integer> count =new HashMap<>();

    }
}
